// 快速排序

#include <iostream>
#include <algorithm>
#include "insertSort.hpp"

// 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48

// // Hoare版本
// void quickSort(int arr[], int left, int right)
// {
//     if(left >= right) return;
//     int begin = left;
//     int end = right;
//     int keyIndex = begin;
//     while(begin < end)
//     {
//         while(begin < end && arr[end] >= arr[keyIndex]) --end; // 右边找小
//         while(begin < end && arr[keyIndex] >= arr[begin]) ++begin; // 左边找大
//         std::swap(arr[begin], arr[end]); // 左边大和右边小交换
//     }
//     std::swap(arr[keyIndex], arr[begin]); // begin和end指针相遇
//     keyIndex = begin; // 重置keyIndex
//     quickSort(arr, left, keyIndex - 1);
//     quickSort(arr, keyIndex + 1, right);
// }

int getMidIndex(int arr[], int left, int right)
{
    int mid = (left + right) / 2;
    if (arr[left] < arr[mid])
    {
        if (arr[mid] < arr[right])
            return mid;
        else if (arr[left] > arr[right])
            return left;
        else
            return right;
    }
    else
    {
        if (arr[mid] > arr[right])
            return mid;
        else if (arr[right] > arr[left])
            return left;
        else
            return right;
    }
}

// // 优化Hoare版本
// void quickSort(int arr[], int left, int right)
// {
//     if (left >= right)
//         return;
//     if (right - left + 1 < 10) // 局部直接有序
//     {
//         insertSort(arr + left, right - left + 1);
//     }
//     else
//     {
//         // 对有序进行优化
//         int mid = getMidIndex(arr, left, right);
//         std::swap(arr[left], arr[mid]);

//         int begin = left;
//         int end = right;
//         int keyIndex = left;
//         while (begin < end)
//         {
//             while (begin < end && arr[end] >= arr[keyIndex])
//                 --end; // 右边找小
//             while (begin < end && arr[keyIndex] >= arr[begin])
//                 ++begin;                     // 左边找大
//             std::swap(arr[begin], arr[end]); // 左边大和右边小交换
//         }
//         std::swap(arr[keyIndex], arr[begin]); // begin和end指针相遇
//         keyIndex = begin;                     // 重置keyIndex
//         quickSort(arr, left, keyIndex - 1);
//         quickSort(arr, keyIndex + 1, right);
//     }
// }

// 双指针版本
void quickSort(int arr[], int left, int right)
{
    if(left >= right) return;

}
